import java.util.Arrays;

public class Test {
    public static void main(String[] args) {

    }
    public static int func4(int[] array){
        Arrays.sort(array);
        return array[array.length/2];
    }

  public static int[] findNum(int[] array,int target){
        int[] ret = {-1,-1};
        for(int i = 0;i<array.length;i++){
            for(int j = i+1;j<array.length;j++){
                if(array[i]+array[j]==target){
                    ret[0]=i;
                    ret[1] = j;
                }
            }
        }
        return ret;
  }

    public static int  binarySearch(int[] array,int key){

        int i = 0;
        int j = array.length-1;
        while(i<=j){
            int mid = (i+j)/2;
            if(array[mid]<key){
             i = mid+1;
            }else if(array[mid]==key){
                return mid;
            }else {
               j = mid-1;
            }
        }
        return  -1;
    }

    public static void func3(int[] array){
        int i = 0;
        int j = array.length-1;
        while(i<j){
            while(i<j&&array[i]%2!=0){
                i++;
            }
            while (i<j&&array[j]%2==0){
                j--;
            }
            int tmp = array[i];
            array[i] = array[j];
            array[j] =tmp;
        }
    }
    public static void move(char pos1,char pos3){
        System.out.println(pos1+"=>"+pos3);
    }
    public static void hanio(int n,char pos1,char pos2,char pos3){
        if(n==1){
            move(pos1,pos3);
            return;
        }
        hanio(n-1,pos1,pos3,pos2);
        move(pos1,pos3);
        hanio(n-1,pos2,pos1,pos3);
    }
    public static void reverse(int[] array) {
        if(array==null){
            return;
        }
        int i = 0;
        int j = array.length-1;
        while(i<j){
            int tmp =array[j];
            array[j] = array[i];
            array[i]=tmp;
            i++;
            j--;
        }
    }
    {

    }
    static {

    }
    public static void BubbleSort(int[] array){
        if(array==null){
            return;
        }
        for(int i = 0;i<array.length-1;i++){
            boolean flg = false;
            for(int j = 0;j<array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1]= tmp;
                    flg=true;
                }
            }
            if(!flg){
                return;
            }
        }
    }
    public static void main1(String[] args) {
        int[] array = {1, 2, 3, 4, 9, 8};

        Arrays.sort(array,0,4);//左闭右开
        String ret = Arrays.toString(array);
        System.out.println(ret);
        //System.out.println(ret);
        // BubbleSort(array);
        reverse(array);
        ret = Arrays.toString(array);
        System.out.println(ret);
    }

    public static int fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        int f1 = 1;
        int f2 = 1;
        int f3 = 1;
        for (int i = 3; i <= n; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;

    }
}
